This invention relates to memory management systems, and more particularly, to apparatus for reordering the sequence of data in a serial shift register type of memory.
Historically, in any serial type of memory, as for example a magnetic tape, it was necessary to examine each item of data serially until the desired item was found. To reduce this access time, many schemes were devised. The magnetic drum with multiple tracks and access heads was one such solution. The random access magnetic disc storage device was another.
Other prior art workers have sought a solution through data management. This broad class seeks to predict the future requirements for access to the data and group together in close proximity those items which are most likely to be required. One criterion for the rearrangement of data is to promote the most recently accessed data to the head of the file. The instant invention constitutes an improvement upon that basic concept.
It is to this latter class of solutions that the instant invention is directed. While, as will be discussed, other prior art memory management systems have promoted the most recently accessed data sets to the head of the file as is done in the instant apparatus, none of them strives to optimize the searching procedure itself to find the sought data to promote to the head of the file.
The invention is generic to any serial type of memory where the data sets are serially shifted, parallel-by-bit, into at least one access station in either a forward or reverse direction of feed. Memories of this type include cascaded bi-stable shift register stages or a so-called bubble memory. Both types are represented in the art now to be discussed.
A serial memory data reordering scheme employing a magnetic bubble memory is described by Beausoleil et al in an article entitled, "Magnetic Bubble Organization," published in the IBM Journal Of Research and Development for November 1972, beginning at page 587. In that publication and in the patents to be hereinafter cited, reordering is effected by shifting in the forward direction until the sought page resides in the input/output station where it is read out to the CPU or other utilization device. The data is then reverse shifted in a loop shortened by one stage, leaving the found page the I/O station. When the head of the file is reached, the I/O station is included in the loop to promote the found page to the head of the file. Searching is then resumed until the next page is found.
In another embodiment, Beausoleil et al describe a double ordering scheme where the odd pages are shifted to the front of the file and the even pages to the rear of the file, with searching proceeding in opposite directions for the odd and even pages. The least recently used pages occupy the center of the file.
In yet another scheme, the publication describes a two-dimensional scheme. Here, in addition to a vertical shift in either a long or short loop, the pages can be shifter laterally betweem the I/O stations in either a short or long loop.
The work of others in the field is represented by the following patents:
a. U.S. Pat. No. 3,701,132 issued Oct. 24, 1972 to Bonyhard et al and assigned to Bell Telephone Laboratories, Inc. PA1 b. U.S. Pat. No. 3,737,881 issued June 5, 1973 to Cordi et al and assigned to the IBM Corporation. PA1 c. U.S. Pat. No. 3,704,452 issued Nov. 28, 1972 to Beausoleil et al and assigned to IBM Corporation. PA1 d. U.S. Pat. No. 3,766,534 issued Oct. 16, 1973 to Beausoleil et al and assigned to the IBM Corporation. PA1 e. U.S. Pat. No. 3,797,002 issued Mar. 12, 1974 to David T. Bowen and assigned to IBM Corporation. PA1 1. The search is bidirectional. PA1 2. A plurality of data sets are searched during each direction of a search. PA1 3. As a data set is found, its search query is replaced by another. PA1 4. Provision is made for diverting a plurality of data sets found during the search for reordering at the head of the file. PA1 5. The direction of search proceeds in a first direction of search until all of the data sets identified for search at the head of the file have been found.
All of the foregoing patents and the publication enjoy the common feature of promoting the most recently accessed data to a preferred position at the head of the file. In the simplest scheme, the data is circulated past a read station until the desired page is found. It is then parked at the read station while the direction of shifting is reversed to bring the head of the file adjacent the read station where the "found" item of data is fed into the stream of data at the head of the file. A counter is usually employed to keep track of the shifts.
In another scheme, the even-numbered pages are promoted to the head of the file and the odd-numbered pages are reordered at the end of the file in accordance with their use. This, effectively, halves the average access time.
Other double ordering schemes are described by Beausoleil et al in the U.S. Pat. No. 3,766,534 patent and by Bonyhard et al in the U.S. Pat. No. 3,701,132 patent supra.
The instant invention constitutes an improvement of the data management systems represented in the foregoing art in these respects:
It is therefore an object of this invention to provide an improved data management system for reordering the sequence of the data sets in a serial shift register type of memory.
A further object is to provide a system in accordance with the first object wherein the data in memory is seriately examined at a search station for conformity with any one of a plurality of search criteria during each of two directions of search, another criterion being substituted for one found during either direction of search, the found data sets being relocated to a position at the head of the file, and reversals of the direction of search occurring when the head of the file occupies the search station and when all of the search criteria then existing have been satisfied.
The foregoing and other objects, features, and advantages of the present invention will be apparent from the following more particular description of a preferred embodiment of the invention as illustrated in the accompanying drawings.